/**
 * 二叉排序树，平衡二叉排序树，红黑树的基类实现
 */

#pragma once

#include <iostream>
#include <string>

enum class NodeType : int { ROOT = -1, LEFT = 0, RIGHT = 1 };

template <typename K, typename V>
class Tree {
 protected:
  Tree<K, V>* p{nullptr};  // 父节点指针
  Tree<K, V>* l{nullptr};  // 左孩子指针
  Tree<K, V>* r{nullptr};  // 右孩子指针

  K* k{nullptr};  // 键指针
  V* v{nullptr};  // 值指针

  NodeType type{NodeType::ROOT};  // 身份标识
  bool is_nil{true};              // nil节点标识

  // 新建nil节点
  // 返回其指针
  virtual Tree<K, V>* new_nil() = 0;

  // 在以this为根的子树中定位key位置
  // 若存在，返回位置
  // 若不存在，返回应该插入的位置
  const Tree<K, V>* locate(const K* key) const {
    if (!key) {
      std::cout << "[Error] " << __func__ << "只能查询非空key" << std::endl;
      return nullptr;
    }
    if (is_nil || *key == *k) {
      return this;
    } else if (*key < *k) {
      return l->locate(key);
    } else {
      return r->locate(key);
    }
  }

  // 以this为根的子树左旋
  // 返回该子树新树根
  virtual Tree<K, V>* left_rotate() {
    // 边界条件检查
    if (is_nil || r->is_nil) {
      std::cout << "[Error] 左旋条件不满足" << std::endl;
      return this;
    }

    Tree<K, V>* oldR = r;         // 保存右孩子
    Tree<K, V>* oldRL = oldR->l;  // 保存右孩子的左子树

    // 1. 右孩子接管当前节点的位置
    if (type == NodeType::LEFT) {
      p->l = oldR;
    } else if (type == NodeType::RIGHT) {
      p->r = oldR;
    }
    oldR->p = p;
    oldR->type = type;  // 右孩子继承当前节点的类型

    // 2. 当前节点成为右孩子的左孩子
    oldR->l = this;
    p = oldR;
    type = NodeType::LEFT;

    // 3. 右孩子的左子树成为当前节点的右子树
    r = oldRL;
    oldRL->p = this;
    oldRL->type = NodeType::RIGHT;

    return oldR;  // 返回新的根
  }
  // 以this为根的子树右旋
  // 返回该子树新树根
  virtual Tree<K, V>* right_rotate() {
    // 边界条件检查
    if (is_nil || l->is_nil) {
      std::cout << "[Error] 右旋条件不满足" << std::endl;
      return this;
    }

    Tree<K, V>* oldL = l;         // 保存左孩子
    Tree<K, V>* oldLR = oldL->r;  // 保存左孩子的右子树

    // 1. 左孩子接管当前节点的位置
    if (type == NodeType::LEFT) {
      p->l = oldL;
    } else if (type == NodeType::RIGHT) {
      p->r = oldL;
    }
    oldL->p = p;
    oldL->type = type;  // 左孩子继承当前节点的类型

    // 2. 当前节点成为左孩子的右孩子
    oldL->r = this;
    p = oldL;
    type = NodeType::RIGHT;

    // 3. 左孩子的右子树成为当前节点的左子树
    l = oldLR;
    oldLR->p = this;
    oldLR->type = NodeType::LEFT;

    return oldL;  // 返回新的根
  }

  // 插入键值对
  // 将当前节点从nil扩展为普通节点并维护对应派生类树的性质
  void insert(const K* key, const V* value) {
    if (!is_nil) {
      std::cout << "[Error] " << __func__ << "只能由nil节点调用" << std::endl;
      return;
    }

    is_nil = false;

    k = new K();
    v = new V();
    *k = *key;
    *v = *value;

    l = new_nil();
    r = new_nil();
    l->p = this;
    l->type = NodeType::LEFT;
    r->p = this;
    r->type = NodeType::RIGHT;

    post_insert();
  }
  // 当前节点被存入kv之后的后处理
  // 包括性质维护等，由派生类实现
  virtual void post_insert() {}

  // 传递删除位置
  // 要求自己是待删除位置
  // 返回最终删除位置
  Tree<K, V>* pass_remove() {
    if (!l->is_nil && !r->is_nil) {
      Tree<K, V>* prev = l;
      while (!prev->r->is_nil) {
        prev = prev->r;
      }
      delete k;
      delete v;
      k = prev->k;
      v = prev->v;
      prev->k = nullptr;
      prev->v = nullptr;
      return prev;
    } else {
      return this;
    }
  }
  // 对最终删除位置执行删除并进行维护
  // 要求自己是最终删除位置
  // 逻辑上是删除自己，底层为拷贝继任删除继任
  void final_remove() {
    if (l->is_nil && !r->is_nil) {
      delete l;
      Tree<K, V>* oldR = r;
      k = oldR->k;
      v = oldR->v;
      oldR->k = nullptr;
      oldR->v = nullptr;
      l = oldR->l;
      r = oldR->r;
      l->p = this;
      r->p = this;
      delete oldR;
    } else if (!l->is_nil && r->is_nil) {
      delete r;
      Tree<K, V>* oldL = l;
      k = oldL->k;
      v = oldL->v;
      oldL->k = nullptr;
      oldL->v = nullptr;
      l = oldL->l;
      r = oldL->r;
      l->p = this;
      r->p = this;
      delete oldL;
    } else {
      delete l;
      delete r;
      l = nullptr;
      r = nullptr;
      delete k;
      delete v;
      k = nullptr;
      v = nullptr;
      is_nil = true;
    }
    post_remove();
  }
  // 当前节点被最终删除kv之后的后处理
  // 包括性质维护等，由派生类实现
  virtual void post_remove() {}

  // 树的基本检查
  bool basic_check() const {
    if (!node_check()) {
      std::cout << "节点属性不合法" << std::endl;
      return false;
    }
    if (!seq_check()) {
      std::cout << "非中序递增" << std::endl;
      return false;
    }
    return true;
  }
  // 节点属性检查
  bool node_check() const {
    bool valid = true;
    if (type == NodeType::LEFT) {
      valid = valid && p && (this == p->l);
    } else if (type == NodeType::RIGHT) {
      valid = valid && p && (this == p->r);
    } else {
      valid = valid && !p;
    }
    if (is_nil) {
      valid = valid && !l && !r && !k && !v;
    } else {
      valid = valid && l && r && k && v && l->node_check() && r->node_check();
    }
    return valid;
  }
  // 中序递增检查
  bool seq_check() const {
    if (type != NodeType::ROOT) {
      std::cout << "[Error] " << "无参版本" << __func__ << "只能由根节点调用"
                << std::endl;
      return false;
    }
    const K* min_key = nullptr;
    const K* max_key = nullptr;
    return seq_check(min_key, max_key);
  }
  bool seq_check(const K*& min_key, const K*& max_key) const {
    if (is_nil) {
      min_key = nullptr;
      max_key = nullptr;
      return true;
    } else {
      const K* l_min_key = nullptr;
      const K* l_max_key = nullptr;
      const K* r_min_key = nullptr;
      const K* r_max_key = nullptr;

      bool left_valid = l->seq_check(l_min_key, l_max_key);
      bool right_valid = r->seq_check(r_min_key, r_max_key);

      // 确定当前子树的最小键和最大键
      min_key = l_min_key ? l_min_key : k;
      max_key = r_max_key ? r_max_key : k;

      // 检查二叉排序树性质：左子树最大值 < 当前键 < 右子树最小值
      bool left_ok = (l_max_key == nullptr) || (*l_max_key < *k);
      bool right_ok = (r_min_key == nullptr) || (*k < *r_min_key);

      return left_valid && right_valid && left_ok && right_ok;
    }
  }
  // 树的额外检查
  // 由派生类实现
  virtual bool extra_check() const { return true; }

  // 树的打印
  void print(std::string indent = "", bool last = true) const {
    std::cout << indent;
    if (last) {
      std::cout << "└─";
      indent += "  ";
    } else {
      std::cout << "├─";
      indent += "| ";
    }

    if (is_nil) {
      // 打印 nil 节点，并显示其额外信息
      std::cout << "nil" << extra_info() << std::endl;
    } else {
      // 打印非 nil 节点
      std::cout << *k << ":" << *v << extra_info() << std::endl;

      // 递归打印左右子树，包括 nil
      l->print(indent, false);
      r->print(indent, true);
    }
  }
  // 树节点的额外信息
  virtual const char* extra_info() const { return ""; }

 public:
  virtual ~Tree() {
    delete k;
    delete v;
  }
  Tree<K, V>* root() {
    Tree<K, V>* t = this;
    while (t->p) t = t->p;
    return t;
  }
  const V* get(const K* key) const {
    if (type != NodeType::ROOT) {
      std::cout << "[Warning] " << __func__ << "只能由根节点调用" << std::endl;
    }
    Tree<K, V>* ptr = const_cast<Tree<K, V>*>(locate(key));
    return ptr->is_nil ? nullptr : ptr->v;
  }
  void set(const K* key, const V* value) {
    if (type != NodeType::ROOT) {
      std::cout << "[Error] " << __func__ << "只能由根节点调用" << std::endl;
      return;
    }
    Tree<K, V>* ptr = const_cast<Tree<K, V>*>(locate(key));
    if (ptr->is_nil) {
      // 插入
      ptr->insert(key, value);
    } else {
      // 更新
      *ptr->v = *value;
    }
  }
  void remove(const K* key) {
    if (type != NodeType::ROOT) {
      std::cout << "[Error] " << __func__ << "只能由根节点调用" << std::endl;
      return;
    }
    Tree<K, V>* ptr = const_cast<Tree<K, V>*>(locate(key));
    if (!ptr->is_nil) {
      ptr = ptr->pass_remove();
      ptr->final_remove();
    }
  }
  bool check() const {
    if (type != NodeType::ROOT) {
      std::cout << "[Error] " << __func__ << "只能由根节点调用" << std::endl;
      return false;
    }
    if (basic_check() && extra_check()) {
      return true;
    } else {
      print();
      return false;
    }
  }
};
